NC102 在二叉树中找到两个节点的最近公共祖先

https://www.nowcoder.com/practice/e0cc33a83afe4530bcec46eba3325116

这题主要还是考察技巧为主，知道了使用 Map 来斩断树形的关系就很好做，思路就是将树转成两个链表去找公共节点。（不过这题把 Java 转成 Golang 的版本还是花了点时间）

func lowestCommonAncestor(root *TreeNode, o1 int, o2 int) int {
    fatherMap := make(map[int]int) // 用来记录每个节点的父亲
    fatherMap[root.Val] = root.Val
    dfs(root, fatherMap) 

    o1M := make(map[int]struct{}) // 用来存 o1 的父节点链
    cur := o1
    // 找到 cur 的父亲们
    for fatherMap[cur] != cur { // 结束条件其实就是 fatherMap[root.Val] == root.Val
        o1M[cur] = struct{}{}
        cur = fatherMap[cur]
    }
    // 别忘了加 root
    o1M[root.Val] = struct{}{}
    cur = o2

    // 遍历 o2 的父节点链，判断 o2 的父亲链哪个跟 o1 的重合了
    for true {
        if _, ok :=  o1M[cur]; !ok {
            cur = fatherMap[cur]
        } else {
            return cur
        }
    }

    return cur
}

// 把所有节点的直接父节点存进去
func dfs(head *TreeNode, m map[int]int) {
    if head == nil {
        return
    }
    if head.Left != nil {
        m[head.Left.Val] = head.Val
    }

    if head.Right != nil {
        m[head.Right.Val] = head.Val
    }

    dfs(head.Left, m)
    dfs(head.Right, m)
}